package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/4ueAj6/description/
 *
 * LCR 029. 循环有序列表的插入
 *
 * 给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。
 *
 * 给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
 *
 * 如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
 *
 * 如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 *
 * 输入：head = [3,4,1], insertVal = 2
 * 输出：[3,4,1,2]
 * 解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。
 *
 *
 * @author hanjuntao
 * @date 2025/8/2 0002
 */
public class LCR_029_4ueAj6 {

    public static void main(String[] args) {
//        // 1, 插入0
//        Node head = new Node(1);
//        insert2(head, 0);
//        System.out.println(head);
//
//        // 1, 插入2
//        head = new Node(1);
//        insert2(head, 2);
//        System.out.println(head);
//
//        // 2-4 插入3
//        head = new Node(2);
//        Node n1 = new Node(4);
//        head.next = n1;
//        n1.next = head;
//        insert2(head, 3);
//        System.out.println(head);
//
//        // 2-3-4 插入1
//        head = new Node(2);
//        Node n11 = new Node(3);
//        Node n12 = new Node(4);
//        head.next = n11;
//        n11.next = n12;
//        n12.next = head;
//        insert2(head, 1);
//        System.out.println(head);
//
//        // 2-3 插入4
//        head = new Node(2);
//        n11 = new Node(3);
//        head.next = n11;
//        n11.next = head;
//
//        insert2(head, 4);
//        System.out.println(head);

        Node head = new Node(3);
        Node n11 = new Node(3);
        Node n12 = new Node(3);
        head.next = n11;
        n11.next = n12;
        n12.next = head;

        insert(head, 0);
        System.out.println(head);
    }

    /**
     * 思路：
     *
     * 由于要插入一个节点，要保证这个节点在循环有序列表中仍然保持有序
     *
     *  由于是非递减的，链表的元素就存在相等的
     *
     *  存在三种场景：
     *
     *  1. 要插入的值位于链表的中间，插入到中间位置  2-4 插入3
     *  2. 要插入的值位于链表的头部，插入到头部位置  2-3-4 插入1
     *  3. 要插入的值位于链表的尾部，插入到尾部位置  2-3 插入4
     *
     * 特殊场景：
     * 1. 链表为空，插入到头部位置
     * 2. 链表只有一个元素，插入到头部位置, 需要形成循环链表
     *
     * 经过思考：
     *
     * 如果不把循环链表断开，情况非常复杂，容易出错
     * 如果断开循环链表，那么就变成单链表了，那么就非常简单了。
     *
     * 算法步骤：
     *
     * 1.遍历链表，找出链表的头节点与尾节点，断开它们（找出出现递减的节点）
     *   a. 情况1：如果只有一个元素，那么头节点与尾节点默认为当前元素
     *   b. 情况2：如果找不到递减的节点，有可能所有的元素都是一样的，出现重复元素，那么将当前传入的元素作为头节点，遍历过程中上一个节点为尾节点
     * 2.从头节点开始遍历单链表，将 x 插入
     * 3.重新把头尾指针连起来
     * 4.返回结果
     *
     *
     * @param head
     * @param insertVal
     * @return
     */
    public static Node insert(Node head, int insertVal) {
        if (head == null) {
            Node newNode = new Node(insertVal);
            newNode.next = newNode;
            return newNode;
        }

        Node realHead = null;
        Node realTail = null;
        Node start = head;
        Node curr = head;
        Node prev = null;

        int size = 0;

        // 遍历循环链表找到断开点
        do {
            size++;

            if (prev != null && curr.val < prev.val) {
                prev.next = null;  // 断开循环链表
                realHead = curr;   // 最小值节点
                realTail = prev;   // 最大值节点
                break;
            }

            prev = curr;
            curr = curr.next;
        } while (curr != start);  // 关键：循环一圈后终止

        // 处理全等值或单节点情况
        if (realHead == null) {
            // 如果只有一个节点，则直接返回
            if (size == 1) {
                realHead = head;
                realTail = head;
                realTail.next = null;
            } else {
                curr = head;
                curr = curr.next;
                prev = null;
                // 如果全等值，将当前节点与上一个节点断开
                while (true) {
                    if (start == curr) {
                        realHead = curr;
                        realTail = prev;
                        realTail.next = null;
                        break;
                    }

                    prev = curr;
                    curr = curr.next;
                }
            }

        }

        // 在断开后的有序链表中插入新节点
        curr = realHead;
        prev = null;
        boolean inserted = false;

        while (curr != null) {
            if (curr.val >= insertVal) {
                Node newNode = new Node(insertVal);
                if (prev == null) {  // 插入到头部
                    newNode.next = realHead;
                    realHead = newNode;
                } else {  // 插入到中间
                    prev.next = newNode;
                    newNode.next = curr;
                }
                inserted = true;
                break;
            }
            prev = curr;
            curr = curr.next;
        }

        // 处理插入值最大的情况（插入尾部）
        if (!inserted) {
            Node newNode = new Node(insertVal);
            realTail.next = newNode;
            realTail = newNode;  // 更新尾节点
        }

        // 重新连接成循环链表
        realTail.next = realHead;

        // 保持原始头节点不变
        return head;
    }


    public static Node insert2(Node head, int insertVal) {
        Node newNode = new Node(insertVal);
        // 处理空链表
        if (head == null) {
            newNode.next = newNode;
            return newNode;
        }

        Node prev = head;
        Node curr = head.next;

        // 遍历循环链表（至少一圈）
        do {
            // 情况1：在正常升序位置插入
            if (prev.val <= insertVal && insertVal <= curr.val) {
                break;
            }

            // 情况2：在尾节点和头节点之间插入
            if (prev.val > curr.val) {
                if (insertVal >= prev.val || insertVal <= curr.val) {
                    break;
                }
            }

            prev = curr;
            curr = curr.next;
        } while (prev != head);  // 回到起点时停止

        // 插入新节点
        prev.next = newNode;
        newNode.next = curr;

        return head;  // 保持原始头节点
    }

    static class Node {
        public int val;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }
}
